// https://leetcode.cn/problems/single-number-iii/
// Created by ade on 2022/9/14.
// 给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//
//你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> singleNumber(vector<int> &nums) {
        if (nums.size() <= 2) return nums;
        vector<int> res = {};
        sort(nums.begin(), nums.end());
        if (nums[0] != nums[1]) res.push_back(nums[0]);
        for (int i = 1; i < nums.size() - 1; i++) {
            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
                res.push_back(nums[i]);
                if (res.size() == 2) break;
            }
        }
        if (res.size() != 2) res.push_back(nums[nums.size() - 1]);
        return res;
    }
};

int main() {
    Solution so;
    vector<int> nums = {0, 4, 3, 0, 4};
    cout << so.specialArray(nums);
    return 0;
}